#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 6234. 最小公倍数为 K 的子数组数目 显示英文描述
通过的用户数516
尝试过的用户数730
用户总通过次数516
用户总提交次数976
题目难度Medium
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

 *
 * */
//求最大公约数
int gcb(int a, int b) {
    int c = 0;
    while (c = a % b) {
        a = b;
        b = c;
    }
    return b;
}

int isB(vector<int> &vec) {
    unsigned lcm = 1;
    for (int i = 0; i < vec.size(); i++) {
        lcm = lcm * vec[i] / (__gcd(lcm, vec[i])); //求最小公倍数
    }

    return lcm;
}

int subarrayLCM(vector<int> &nums, int k) {

    int count = 0;

    for (int i = 0; i < nums.size(); ++i) {

        for (int j = i; j < nums.size(); ++j) {
            vector<int> s(nums.begin() + i, nums.begin() + j + 1);
            if (isB(s) == k)
                count++;
        }
    }

    return count;
}

//我上面那个过不去应该是切分数组的原因.................
int subarrayLCM(vector<int> &nums, int k) {
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        //if(nums[i] == k) ans++;
        int t = nums[i];
        for (int j = i; j < n; j++) {
            t = lcm(nums[j], t);//每次继续求最小公共倍数就行
            if (t == k) ans++;
        }
    }
    return ans;
}